//
// Created by Semir on 2020/6/5.
//

#include <iostream>
#include <vector>

using namespace std;

int inversePairsCnt;

void MergeAndCount(vector<int>& arr, int begin, int mid, int end) {
    int i = begin;
    int j = mid + 1;
    vector<int> tmpArr(end - begin + 1);
    int k = 0;
    int leftCnt = mid - begin + 1;
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            tmpArr[k++] = arr[i++];
            leftCnt--;
        } else {
            tmpArr[k++] = arr[j++];
            inversePairsCnt += leftCnt;
        }
    }
    while (i <= mid) {
        tmpArr[k++] = arr[i++];
    }
    while (j <= end) {
        tmpArr[k++] = arr[j++];
    }
    i = begin;
    k = 0;
    while (k < tmpArr.size()) {
        arr[i++] = tmpArr[k++];
    }
    vector<int>().swap(tmpArr);
}

//void Merge(vector<int>& arr, int begin, int mid, int end) {
//    int i = begin;
//    int j = mid + 1;
//    vector<int> tmpArr(end - begin + 1);
//    int k = 0;
//    while (i <= mid && j <= end) {
//        if (arr[i] <= arr[j]) {
//            tmpArr[k++] = arr[i++];
//        } else {
//            tmpArr[k++] = arr[j++];
//        }
//    }
//    while (i <= mid) {
//        tmpArr[k++] = arr[i++];
//    }
//    while (j <= end) {
//        tmpArr[k++] = arr[j++];
//    }
//    i = begin;
//    k = 0;
//    while (k < tmpArr.size()) {
//        arr[i++] = tmpArr[k++];
//    }
//    vector<int>().swap(tmpArr);
//}

void SplitAndMerge(vector<int>& arr, int begin, int end) {
    if (begin >= end) {
        return;
    }
    int mid = begin + (end - begin) / 2;
    SplitAndMerge(arr, begin, mid);
    SplitAndMerge(arr, mid + 1, end);
    MergeAndCount(arr, begin, mid, end);
}

//void MergeSort(vector<int>& arr) {
//    if (arr.empty()) {
//        return;
//    }
//    int mid = arr.size() / 2;
//    SplitAndMerge(arr, 0, mid);
//    SplitAndMerge(arr, mid + 1, arr.size() - 1);
//    Merge(arr, 0, mid, arr.size() - 1);
//}

int InversePairs(vector<int> data) {
    inversePairsCnt = 0;
    if (data.empty()) {
        return inversePairsCnt;
    }
    int mid = data.size() / 2;
    SplitAndMerge(data, 0, mid);
    SplitAndMerge(data, mid + 1, data.size() - 1);
    MergeAndCount(data, 0, mid, data.size() - 1);
    return inversePairsCnt % 1000000007;
}

int main() {
    vector<int> arr = {1,2,3,4,5,6,7,0};
    int res = InversePairs(arr);
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl << res << endl;
    return 0;
}